/**
 * 你这个学期必须选修numCourse门课程，记为0到numCourse - 1
 * 在选修某些课程之前需要先修一些课程，先修课程按数组prerequisites给出，其中
 * prerequisites[i] = [ai, bi],表示如果要学习课程ai则必须先学习课程bi
 * * 例如，先修课程对[0, 1]表示: 想要学习课程0，你需要先完成课程i
 *   请你判断是否可能完成所有课程的学习？如果可以。返回true; 否则，返回false
 * 示例1:
 *  输入: numCourses = 2, prerequisites = [[1, 0]]
 *  输出: true
 *  解释: 总共有两门课程，学习课程1之前，你需要完成课程0，这是可能的
 * 示例2:
 *  输入: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
 *  输出: false
 *  解释: 总共有两门课程，学习课程1之前，你需要完成课程0的学习；并且学习课程0之前，你还应学习课程1，这是不可能的
*/
function canFinish (numCourses, prerequisites) {
    // 如果没有依赖关系则直接返回true
    if (!prerequisites.length) return true;
    // 入度关系
    const inDep = new Array(numCourses).fill(0);
    // 邻接表关系
    const map = new Map();
    // 遍历目标课程数组
    for (let i = 0; i < prerequisites.length; i++) {
        const [ form, to ] = prerequisites[i];
        // 为各门课程设置入度
        inDep[form]++;
        // 设置邻接表关系
        if (map.get(to)) {
            map.set(to, [ ...map.get(to), form ]);
        } else {
            map.set(to, [ form ])
        }

    }
    // 找到入度为0的课程
    let queue = [];
    for (let i = 0; i < inDep.length; i++) {
        if (inDep[i] === 0) {
            queue.push(i);
        }

    }
    while (queue.length) {
        const target = queue.shift();
        numCourses--;
        if (!map.get(target)) {
            continue;
        }
        queue = [...queue, ...map.get(target)];
    }
    return numCourses === 0;
}

console.log(canFinish(2, [[1, 0]]));
console.log(canFinish(2, [[1, 0], [0, 1]]));